This application claims priority to Korean Patent Application No. 2002-36626, filed on Jun. 28, 2002, the contents of which are herein incorporated by reference in their entirety.
1. Field of the Invention
The present invention relates to a content addressable memory cell (hereinafter referred to as xe2x80x9cCAM cellxe2x80x9d) and, more particularly, to a ternary content addressable memory cell (hereinafter referred to as xe2x80x9cTCAM cellxe2x80x9d) capable of storing three states of information.
2. Discussion of Related Art
A CAM is a memory which is addressed by its own contents. Different from a RAM or ROM wherein an address is used to indicate a specific position in its memory cell array and outputs data stored in the addressed position, a CAM is externally supplied with data, and searches are made within the contents of the CAM for a match with the supplied data, and outputs an address depending on a comparison result. Each cell of a CAM includes comparison logic. A data value input to the CAM is compared with data stored in all the cells simultaneously. The matched result is the address. A CAM is commonly used in applications requiring fast searches for a pattern, a list, image data, etc.
A CAM cell may be classified into a binary CAM cell and a TCAM cell. A typical binary CAM cell is configured with a RAM cell to store one of two states of information, i.e., a logic xe2x80x9c1xe2x80x9d state and a logic xe2x80x9c0xe2x80x9d state. The binary CAM cell includes a compare circuit that compares data supplied externally (hereinafter, xe2x80x98comparand dataxe2x80x99) with data stored in the RAM cell and drives a corresponding match line to a predetermined state when the comparand data and the stored data are matched. Examples of the binary CAM cells are disclosed in U.S. Pat. No. 4,646,271 entitled xe2x80x9cCONTENT ADDRESSABLE MEMORY HAVING DUAL ACCESS MODExe2x80x9d, U.S. Pat. No. 4,780,845 entitled xe2x80x9cHIGH DENSITY, DYNAMIC, CONTENT-ADDRESSABLE MEMORY CELLxe2x80x9d, U.S. Pat. No. 5,490,102 entitled xe2x80x9cLOW CAPACITANCE CONTENT-ADDRESSABLE MEMORY CELLxe2x80x9d, and U.S. Pat. No. 5,495,382 entitled xe2x80x9cCONTENTS ADDRESSABLE MEMORYxe2x80x9d.
A TCAM cell can store one of three states of information, i.e., a logic xe2x80x9c1xe2x80x9d state, a logic xe2x80x9c0xe2x80x9d state, and a xe2x80x9cdon""t carexe2x80x9d state. The TCAM cell includes a main RAM cell to store one of two states of information, i.e., a logic xe2x80x9c1xe2x80x9d state or a logic xe2x80x9c0xe2x80x9d state, and a mask RAM cell to store local mask data. A comparison result of comparand data with data stored in the main RAM cell is masked with the mask data such that the comparison result does not affect a corresponding match line. Such a TCAM cell offers the user more flexibility to determine what data bits in a word will be masked during a compare operation. TCAM cells are further described, for example, in U.S. Pat. No. 6,044,055 entitled xe2x80x9cCONTENT ADDRESSABLE MEMORY STORAGE DEVICExe2x80x9d and U.S. Pat. No. 6,514,384 entitled xe2x80x9cTERNARY CONTENT ADDRESSABLE MEMORY CELLxe2x80x9d. FIG. 1 shows a conventional TCAM cell which includes a main memory cell having two NMOS transistors T1 and T2 and two inverters INV1 and INV2, a compare circuit consisting of three NMOS transistors T3, T4, and T5, a mask circuit consisting of an NMOS transistor T6, and a mask memory cell consisting of two NMOS transistors T7 and T8 and two inverters INV3 and INV4. The TCAM cell shown in FIG. 1 is described in U.S. Pat. No. 6,154,384. Signal lines represented as xe2x80x9cBLxe2x80x9d and xe2x80x9cBLBxe2x80x9d are used for data transmission of a main memory cell. Signal lines represented as xe2x80x9cCLxe2x80x9d and xe2x80x9cCLBxe2x80x9d are used for comparand data transmission. Signal lines represented as xe2x80x9cMLxe2x80x9d and xe2x80x9cMLBxe2x80x9d are used for mask data transmission of a mask memory cell. A TCAM is made from TCAM cells arranged in a matrix of rows and columns. TCAM cells in a row constitute one word, which may be 32, 64, 128 bits, or higher. Transistors T5 and T6 of the respective TCAM cells in a row constitute a wired-OR logic for a match line MATCH.
Although TCAMS afford advantages such as speedy access for numerous applications, drawbacks do exist. For example, when comparand data of the TCAM cell of FIG. 1 is not matched with data stored in a main memory cell, a discharge operation of a match line is carried out. Because the occurrence of unmatched words is usually greater than the occurrence of matched words, match lines (MATCH) corresponding to the unmatched words are frequently discharged, and more power is thereby consumed.
Another problem is shown in FIG. 2A. A logic high level at node DX of FIG. 1 (VCL-Vtn4 or VCLB-Vtn3, wherein VCL represents a voltage of a CL line, VCLB represents a voltage of a CLB line, and the Vtn3 and Vtn4 represent threshold voltages of transistors T3 and T4, respectively) approaches a voltage only slightly higher than the threshold voltage of transistor T3 or T4. This high level voltage at DX is used to turn on transistor T5. To compensate for the lowered high voltage level, a big-sized transistor T5 must be used. The need for a bigger size transistor in each cell lowers the overall density of the TCAM. Even more problematic, if an operation voltage is lowered, the TCAM cell may not operate properly as the high level voltage at DX fails to meet the threshold voltage of transistor T5. For illustration, assuming that an operation voltage is 1.2V and a threshold voltage of an NMOS transistor T5 is 0.5V, a high level of the DX node thus becomes 0.7V, as shown in FIGS. 2A and 2B. Since this level is not high enough to turn on the NMOS transistor T5, the signal level on match line MATCH cannot be used to properly indicate a match or no-match.
Referring back to the TCAM cell of FIG. 1, if the compare result is not masked (by transistor T6), transistor T5 is turned off when comparand data is matched to data stored in a main memory cell and is turned on when there is no match. That is, when there is a match, a match line MATCH is maintained at a precharge state. When there is no match, charges of the match line are discharged through transistors T5 and T6. The discharge speed of the match line MATCH is a function of the number of unmatched bits in one word. For example, when only one bit of one word is unmatched, the charges of the match line MATCH are discharged through the transistors T5 and T6 of the unmatched TCAM cell. When n bits are unmatched among an m-bit word (n being a positive integer smaller than m), the charges of the match line MATCH are discharged through transistors nx (T5, T6) in n TCAM cells. The time needed to discharge the match line MATCH varies depending on the number of mismatched cells. To minimize the discharge speed variation, larger sized transistors T5 and T6 are needed. This, however, results in larger size TCAM cells. Therefore, a discharge speed difference also negatively affects the density of a TCAM.
In view of the foregoing, a need exists for a content addressable memory cell that is stably operable at low operation voltage, low power consumption, and facilitates manufacture of a high density CAM.
According to an aspect of the present invention, a ternary content addressable memory (TCAM) having an array of cells arranged in rows and columns is provided, each cell comprising: a main memory cell for storing a data bit and its complement and a pair of bit lines for carrying the data bit and its complement; a compare circuit having a pair of compare lines and an output node, the compare circuit coupled to the main memory cell for comparing the data bit and its complement with corresponding compare lines and outputting a compared signal at the output node; a match circuit coupled to the output node of the compare circuit and a match input line and a match output line, the match circuit for selectively connecting the match input line to the match output line based on the compared signal; a mask memory cell for storing and outputting mask data; and a mask circuit coupled to the match circuit and the match input line and the match output line for masking the compared signal or for selectively connecting the match input line to the match output line based on the mask data.
Preferably, the compare circuit includes a pair of PMOS transistors, and the pair of PMOS transistors are correspondingly coupled to the pair of compare lines and commonly connected at the output node of the compare circuit. Further, each of the match circuit and the mask circuit includes an NMOS transistor, wherein the NMOS transistors of the match circuit and the mask circuit are commonly connected at the match input line and the match output line. In one embodiment, the match input line is connected to the match output line upon an indication of a match from the compared signal.
According to another aspect of the invention, the match input line is connected to the match output line upon an indication of a mask condition from the mask data. The match input line is also preferably cascaded from and connected to a match output line of a preceding cell or the match output line is cascaded and connected to a match input line of a subsequent cell along the same row. The TCAM further includes a discharge circuit coupled to ground and to the match input line of the first cell of the same row and a precharge circuit coupled to a preset voltage and to the match output line of the last cell of the same row, wherein when all cells of the same row output a match, all the match input and output lines of the same row are discharged to substantially ground. According to this embodiment, the compare circuit includes a pair of PMOS and a pair of NMOS transistors, each PMOS transistor being commonly connected to a corresponding NMOS transistor and a corresponding compare line, and each of the match circuit and the mask circuit includes an NMOS transistor.
According to another aspect of the invention, each of the match circuit and the mask circuit includes a PMOS transistor, and the compare circuit includes a pair of NMOS transistors. The PMOS transistors are commonly connected at the match input line and at the match output line. The TCAM of this embodiment further includes a precharge circuit coupled to a preset voltage and to the match input line of the first cell of the same row and a discharge circuit coupled to ground and to the match output line of the last cell of the same row, wherein when all cells of the same row output a match, all the match input and output lines of the same row are precharged to substantially the preset voltage.
Preferably, the main memory cell and the mask memory cell are at least one of SRAM, DRAM, or nonvolatile memory (NVM) cells. The TCAM further includes a main word line and a mask word line which are connected to each other. Further, each of the match circuit and the mask circuit includes a PMOS transistor.
According to another embodiment of the invention, a content addressable memory (CAM) having an array of cells arranged in rows and columns is provided, each cell comprising: a main memory cell for storing a data bit and its complement and a pair of bit lines for carrying the data bit and its complement; a compare circuit having a pair of compare lines and an output node, the compare circuit coupled to the main memory cell for comparing the data bit and its complement with corresponding compare lines and outputting a compared signal at the output node; a match circuit coupled to the output node of the compare circuit and a match input line and a match output line, the match circuit for selectively connecting the match input line to the match output line based on the compared signal; a discharge circuit coupled to ground; a precharge circuit coupled to a preset voltage; the discharge circuit or the precharge circuit coupled to the match input line of the same row or the match output line of the same row, wherein when all cells of the same row output a match, all the match input and output lines of the same row are either precharged or discharged.
Preferably, the compared circuit includes a pair of PMOS transistors and the match circuit includes a NMOS transistor. According to an alternative embodiment, the compare circuit includes a pair of NMOS transistors and the match circuit includes a PMOS transistor.
Preferably, the TCAM further includes a mask circuit coupled to the match circuit and the match input line and the match output line for masking the compared signal or for selectively connecting the match input line to the match output line based on a mask data. A memory controller is further included for providing operation mode to the CAM.
A method is also provided for operating a content addressable memory (CAM) having an array of cells arranged in rows and columns, comprising the steps of: storing in a main memory cell a data bit and its complement; comparing the data bit and its complement with signals at corresponding compare lines and outputting a compared signal; selectively connecting a match input line to a match output line based on an indication of a match from the compared signal to form a match line; and setting the match line at a first voltage level when all of memory cells of the same row are matched, wherein said first voltage is a ground voltage or a power supply voltage.
These and other aspects and features of the present invention will become more apparent from the fully detailed description of preferred embodiments when read in connection with the accompanying drawings.